package algorithm.leetcode.I201to400;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 最大整除子集
 * 要求返回给定无重复正整数数组的一个子集,子集中的*任意*元素对a,b满足 a%b == 0 或者 b%a==0
 * 如果有多个则返回一个即可
 * 不妨假设 a>b, 并将结果子集排序, 显然最后的子集后一个元素肯定整数倍于前一个元素
 *
 */

// 如果整数a是整除子集 S1 中的最小整数 b 的约数, 即 a|b ,那么 a 可以添加到S1中得到更大的整除子集
// 如果整数c是整除子集 S2 中的最大整数 d 的倍数, 即 d|c ,那么 c 可以添加到S2中得到更大的整除子集
//
// 定义: dp[i] 表示在输入数组 nums 升序排列的前提下，以 nums[i] 为最大整数的「整除子集」的大小（在这种定义下 nums[i] 必须被选择）
// 状态转移: 枚举 j = 0...i−1 的所有整数 nums[j]，如果 nums[j] 能整除 nums[i]，说明 nums[i] 可以扩充在以 nums[j] 为最大整数的整除子集里成为一个更大的整除子集
// 初始化: dp[i] = 1, 即任意一个数单独可以构成整除子集



public class Q368 {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int maxSubsetSize = 1;

        // 维护dp数组
        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) if (nums[i] % nums[j] == 0) dp[i] = Math.max(dp[j] + 1, dp[i]);
            maxSubsetSize = Math.max(dp[i], maxSubsetSize);
        }

        // 倒推得到结果
        // nums 2  4  7  8  9  12 16 20
        // dp   1  2  1  3  1  3  4  3
        // maxSubsetSize = 4, maxIndex = 6
        List<Integer> result = new LinkedList<>();
        int maxVal = 0;
        for (int i = nums.length-1; i >= 0; i--) {
            if (dp[i] == maxSubsetSize && maxVal % nums[i] == 0) {
                maxVal = nums[i];
                result.add(maxVal);
                maxSubsetSize--;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Q368 q368 = new Q368();
        System.out.println(q368.largestDivisibleSubset(new int[]{1, 2, 4, 8, 5, 15, 45, 135, 405}));
    }
}
